package com.atguigu.structures.tree;

import com.atguigu.structures.tree.node.TreeNode;

/**
 * @author xr-8
 * @date 2022-09-21
 * @time 23:45
 */
public class TreeTest {

    public static void main(String[] args) {
//        binaryTreeTest();
//        arrayBinaryTreeTest();
        threadBinaryTreeTest();
    }

    /**
     * 测试二叉树，遍历、查找、删除
     */
    public static void binaryTreeTest() {
        //先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的结点
        TreeNode root = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "吴用");
        TreeNode node3 = new TreeNode(3, "卢俊义");
        TreeNode node4 = new TreeNode(4, "林冲");
        TreeNode node5 = new TreeNode(5, "关胜");

        //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);

        // 遍历
//        binaryTree.preOrder();
        binaryTree.infixOrder();
//        binaryTree.postOrder();

        // 查找
//        binaryTree.preOrderSearch(4) ;
        binaryTree.infixOrderSearch(2);
//        binaryTree.postOrderSearch(3);

        // 删除
        System.out.println("删除前,前序遍历");
        binaryTree.preOrder(); //  1,2,3,5,4
        binaryTree.delNode(2);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder(); // 1,2,3,4
    }

    /**
     * 测试顺序存储的前序遍历
     */
    public static void arrayBinaryTreeTest() {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        //创建一个 ArrBinaryTree
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
    }

    /**
     * 测试线索化二叉树，中序线索化、遍历
     */
    public static void threadBinaryTreeTest() {
        //创建二叉树
        TreeNode root = new TreeNode(1, "tom");
        TreeNode node2 = new TreeNode(3, "jack");
        TreeNode node3 = new TreeNode(6, "smith");
        TreeNode node4 = new TreeNode(8, "mary");
        TreeNode node5 = new TreeNode(10, "king");
        TreeNode node6 = new TreeNode(14, "dim");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        // 中序线索化二叉树
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.setRoot(root);
        tree.threadedNodes();

        // 遍历线索化后的二叉树
        tree.threadList();
    }
}
